/*
 * @lc app=leetcode.cn id=1745 lang=typescript
 *
 * [1745] 回文串分割 IV
 */

// @lc code=start
function checkPartitioning(s: string): boolean {
  const n = s.length;
  // 以0为起点，构成回文串的结束下标
  const hash0 = new Set<number>();
  // 以 n -1 为终点，构成回文串的开始下标
  const hashn = new Set<number>();
  // 处理回文串
  const extract = (i: number, j: number) => {
    while (i >= 0 && j < n && s[i] === s[j]) {
      if (i === 0) hash0.add(j);
      if (j === n - 1) hashn.add(i);
      i--, j++;
    }
  };
  // 判断是否有满足题意的三段回文串
  const isCheck = (i: number, j: number): boolean => {
    while (s[i] === s[j]) {
      if (hash0.has(i - 1) && hashn.has(j + 1)) return true;
      i--, j++;
    }
    return false;
  };
  // 预处理
  for (let i = 0; i < n; i++) {
    extract(i, i);
    extract(i, i + 1);
  }

  // 判断是否可以分割
  for (let i = 1; i < n - 1; i++) {
    if (isCheck(i, i) || isCheck(i, i + 1)) return true;
  }

  return false;
}
// @lc code=end
